Optimisasi Konveks: Mendekati Ketidaksamaan: Dari Fungsi Indikator ke Penghalang yang Halus

Bayangkan Anda sedang mengoperasikan algoritma perdagangan frekuensi tinggi. Portofolio Anda memiliki batas risiko yang ketat. Kendala "keras" berfungsi seperti rem darurat—menghentikan semua hal secara tiba-tiba begitu batas tercapai, yang dapat menyebabkan sistem gagal. Dalam optimisasi konveks, kita lebih memilih sistem peringatan "lembut". Kita mengganti tebing biner yang kasar dari fungsi indikator dengan penghalang logaritmik yang halus, yang semakin memberi hukuman pada tujuan seiring kita mendekati batas. Ini memungkinkan optimisator untuk "merasakan" datangnya kendala dan menyesuaikan trajektorinya secara halus tanpa pernah melanggar batas.

Masalah Non-Diferensiasi

Masalah optimisasi terbatas standar didefinisikan sebagai:

$$\text{minimalkan } f_0(x) \\ \text{dengan syarat } f_i(x) \leq 0, \quad i = 1, \ldots, m \\ Ax = b$$

Kita secara teoretis bisa menulis ulang ini menggunakan fungsi indikator $I_-(u)$ untuk menyatukan kendala ke dalam fungsi tujuan. Namun, $I_-(u)$ merupakan monster bagi kalkulus:

$$I_-(u) = \begin{cases} 0 & u \leq 0 \\ \infty & u > 0 \end{cases}$$

Karena fungsi ini tidak kontinu dan memiliki gradien tak hingga di batas, kita tidak dapat menghitung Hessian yang dibutuhkan untuk Metode Newton. Kita membutuhkan pendekatan diferensial.

Penghalusan Logaritmik

Pendekatan

Kita mendekati $I_-(u)$ menggunakan fungsi:

$$\hat{I}_-(u) = -(1/t) \log(-u), \quad \text{dom } \hat{I}_- = -\mathbf{R}_{++}$$

Di sini, $t > 0$ adalah parameter yang menentukan akurasi pendekatan kita. Semakin besar nilai $t$, semakin mirip penghalang tersebut dengan fungsi indikator sejati.

Kendala Interioritas

Berbeda dengan metode set aktif, pendekatan ini mengharuskan setiap iterasi $x$ tetap layak secara ketat ($f_i(x) < 0$). Karena logaritma tidak terdefinisi untuk nilai non-negatif, hal ini menciptakan penghalang yang "tidak dapat ditembus" yang menjaga pencarian tetap di bagian dalam himpunan layak.

🎯 Definisi: Metode Titik Interior

Metode titik interior: metode untuk menyelesaikan masalah optimisasi konveks yang melibatkan kendala ketidaksamaan dengan menerapkan metode Newton pada rangkaian masalah yang dibatasi oleh persamaan.

PERTANYAAN 1

Mengapa kita tidak bisa menggunakan fungsi indikator ideal $I_-(u)$ langsung dengan Metode Newton?

Fungsinya tidak dapat didiferensialkan di batas u=0.

Ini membuat fungsi objektif menjadi tidak konveks.

Ini mengharuskan domain dibatasi pada nilai positif.

Metode Newton hanya bekerja untuk masalah tanpa kendala.

PERTANYAAN 2

Apa efek peningkatan parameter $t$ dalam pendekatan penghalang logaritmik?

Ini membuat pendekatan menjadi lebih halus dan lebih datar.

Ini memperuncing transisi di batas, membuatnya lebih mirip fungsi indikator ideal.

Ini memungkinkan optimisasi untuk melanggar ke daerah yang tidak layak.

Ini mengurangi masalah menjadi kasus pemrograman linier.

PERTANYAAN 3

Manakah dari berikut ini yang merupakan persyaratan wajib untuk titik-titik $x$ dalam metode titik interior menggunakan penghalang logaritmik?

$f_i(x) \ge 0$

$f_i(x) < 0$ untuk semua i

$f_i(x) = 0$ untuk setidaknya satu kendala aktif

Gradien $\nabla f_0(x)$ harus nol

PERTANYAAN 4

Dalam analogi algoritma perdagangan, bagaimana perilaku penghalang logaritmik saat risiko mendekati batas?

Ini menerapkan hukuman yang meningkat secara eksponensial pada fungsi tujuan.

Ini mengabaikan risiko hingga batas benar-benar dilanggar.

Ini mengurangi hukuman untuk mendorong pencarian batas.

Ini mematikan sistem secara langsung.

PERTANYAAN 5

Berapa selisih suboptimalitas untuk titik pada jalur pusat dengan $m$ kendala dan parameter $t$?

$t/m$

$m/t$

$\log(m/t)$

$1/t^2$